﻿package com.colorsstudio.defence.algorithm
{
	import de.polygonal.ds.*;
	
	import flash.events.*;
	import flash.display.*;
	import flash.text.*;
	import flash.utils.*;
	
	public class PathFinder extends MovieClip
	{
		public var graph:Graph;
		
		private var nodeCount:int = 0;
		
		private var nodeQue:LinkedQueue;
		
		private var target0:Node;
		private var target1:Node;
		
		private var traverse:Boolean;
		
		private var timer:Timer;
		
		private var nodeCanvas:Sprite;
		
		private var pos:Array = [];
		private var arc:Array = [];
		
		private var modeTf:TextField;
		
		public var nodes:Array;
		
		public var path:LinkedStack;
		
		private var canvas:Shape;
		
		public function PathFinder()
		{
			stage.scaleMode = StageScaleMode.NO_SCALE;
			stage.align = StageAlign.TOP_LEFT;
			
			nodes = [];
			
			Node.RADIUS = 8;
			//Node.BORDER_CLR_MARK = 0;
			Node.BORDER_CLR_UNMARK = 0xffffff;
			
			nodeQue = new LinkedQueue();
			
			timer = new Timer(1000, 1);
			
			addChild(nodeCanvas = new Sprite());
			
			//addChild(canvas = new Shape());
			
			setupGraph();
			
			modeTf = new TextField();
			modeTf.defaultTextFormat = new TextFormat(GraphBuilder.DEMO_FONT.fontName, 11, 0, false, false, null, null, null, "center");
			modeTf.selectable = false;
			modeTf.background = true;
			modeTf.embedFonts = true;
			modeTf.antiAliasType = "advanced";
			modeTf.text = "select start";
			modeTf.autoSize = "left";
			addChild(modeTf);
			
			var bmpData:BitmapData = new mask_bmpdata(550, 400);
			
			var bitmap:Bitmap = new Bitmap(bmpData);
			
			addChild(bitmap);
			
			//var maskImage:Bitmap = new Bitmap(BitmapData(mask_bmpdata));
		}
		
		/**
		 * builds a pre-recorded graph
		 */
		private function setupGraph():void
		{
			var nodeData:Array = [[386,266],[356,266.55],[310.8,244.25],[317.5,185.15],[389.05,188.3],[387.6,117.9],[313,115.4],[236,66.2],[211,119],[236,165.65],[271.85,165.3],[305,149.4],[217,198.95000000000002],[158.25,211.35000000000002],[122.85000000000001,134.85],[151.5,110.45],[184.4,290.25],[250.25,274.35],[259.8,247.45000000000002],[269.05,340.90000000000003],[319.65000000000003,338.40000000000003],[395.40000000000003,364.25],[445.3,285.3],[481.05,247.45000000000002],[476.45000000000005,181.25],[472.20000000000005,102.65],[355.75,42.5],[332.75,58.050000000000004],[331.35,94.85000000000001],[272.55,88.5],[202,364],[112,317],[58,242],[57,142],[150,30]];
			var  arcData:Array = [[22,23],[22,0],[0,1],[1,2],[2,3],[3,11],[11,6],[6,28],[28,27],[27,26],[6,29],[28,29],[29,7],[7,35],[30,16],[16,17],[19,17],[16,13],[31,16],[32,13],[17,18],[18,12],[12,9],[9,8],[8,7],[9,10],[10,11],[21,20],[20,1],[20,19],[19,30],[30,31],[31,32],[24,4],[4,3],[5,6],[25,5],[21,22],[23,24],[24,25],[25,26],[32,33],[33,14],[13,14],[14,15],[15,8],[15,34],[34,7],[13,12],[0,4],[4,5],[18,2],[26,35],[34,35],[33,34], [20,21],[19,20],[30,19],[16,30],[31,30],[32,31],[13,32],[16,31],[17,16],[17,19],[1,20],[2,1],[1,0],[0,22],[22,21],[23,22],[24,23],[4,24],[4,0],[3,4],[5,4],[5,25],[6,5],[28,6],[6,11],[8,9],[9,12],[12,13],[14,13],[14,33],[33,32],[15,14],[8,15],[7,8],[7,29],[29,6],[29,28],[27,28],[26,27],[35,7],[34,33],[34,15],[7,34],[35,34],[35,26],[26,25],[25,24],[23,24],[13,16],[10,9],[11,10],[11,3],[18,17],[12,18],[2,18],[3,2]];
			
			graph = new Graph(100);
			
			//create nodes
			for (var i:int = 0; i < nodeData.length; i++)
			{
				var x:int = nodeData[i][0];
				var y:int = nodeData[i][1];
				
				var node:Node = new Node(i);
				nodeCanvas.addChild(node);
				node.x = x;
				node.y = y;
				node.addEventListener(MouseEvent.MOUSE_DOWN, onNodePress);
				nodes[i] = node;
				
				node.blendMode = "overlay";
				
				var tf:TextField = node.getChildAt(0) as TextField;
				var tfm:TextFormat = tf.getTextFormat();
				tfm.size = 8;
				tf.defaultTextFormat = tfm;
				
				node.write(i.toString());
				
				//create a waypoint and store it inside a graph node
				var wp:Waypoint = new Waypoint(i);
				wp.setPos(x, y);
				graph.addNode(wp, i);
			}
			
			//create node arcs
			for (i = 0; i < arcData.length; i++)
				graph.addArc(arcData[i][0], arcData[i][1], 1);
			
			
				
			//draw node arcs
			draw();
		}
		
		private function animate(e:TimerEvent):void
		{
			if (path.size > 0)
			{
				var wp:Waypoint = path.peek();
				path.pop();
				
				var node:Node = nodes[wp.graphNodeIndex];
				node.mark();
				
				var gn:GraphNode = graph.nodes[wp.graphNodeIndex];
				
				if (path.size == 0) return;
				
				//draw only the arc that is point to the next waypoint
				var nextWp:Waypoint = path.peek();
				
				if (nextWp)
				{
					drawNodeArcs(gn, graph.nodes[nextWp.graphNodeIndex]);
				}
				else
					drawNodeArcs(gn);
			}
		}
		
		private function onAnimationComplete(e:TimerEvent):void
		{
			traverse = false;
			
			freezeNodes(false);
			unmarkNodes();
			
			target0 = target1 = null;
			draw();
		}
		
		private function onNodePress(e:MouseEvent):void
		{
			var node:Node;
			if (e.target is TextField)
				node = e.target.parent as Node;
			else
				node = e.target as Node;
			
			if (!target0)
			{
				//first click; store starting node 
				target0 = node;
				modeTf.text = "select goal";
			}
			else
			{
				/**********************************************************
				 * path finder
				 *********************************************************/
				
				//second click; store destination node
				target1 = node;
				
				//find path from target0 to target1
				var startNode:GraphNode = graph.nodes[target0.graphIndex];
				var  goalNode:GraphNode = graph.nodes[target1.graphIndex];
				
				if (startNode == goalNode)
				{
					modeTf.text = "Are you serious?";
					target0.unmark();
					target1.unmark();
					target0 = target1 = null;
					return;
				}
				
				var pathExists:Boolean = AStarLine.find(graph, startNode, goalNode);
				
				if (!pathExists)
				{
					modeTf.text = "no path exists from node " + target0.graphIndex + " to " + target1.graphIndex + ", try again."
					target0.unmark();
					target1.unmark();
					target0 = target1 = null;
					return;
				}
				
				modeTf.text = "tracing path from node " + target0.graphIndex + " to " + target1.graphIndex;
				
				//now path contains a stack of waypoints, popping waypoints off
				//the stack goes from start to goal.
				path = AStarLine.getPath(startNode, goalNode);
				trace(path.size);
				trace(path.dump());
				
				target0.unmark();
				target1.unmark();
				target0 = target1 = null;
				
				freezeNodes(true);
				draw();
				nodeCanvas.graphics.lineStyle(2, 0xf40095, 1);
				
				timer = new Timer(100, path.size + 10);
				timer.addEventListener(TimerEvent.TIMER, animate);
				timer.addEventListener(TimerEvent.TIMER_COMPLETE, onAnimationComplete);
				timer.start();
			}
		}
		
		private function draw():void
		{
			nodeCanvas.graphics.clear();
			nodeCanvas.graphics.lineStyle(1, 0xffffff, 1);
			
			//draw all arcs originating from the given node
			for (var i:int = 0; i < graph.nodes.length; i++)
			{
				if (graph.nodes[i])
					graph.breadthFirst(graph.nodes[i], drawNodeArcs);
			}
		}
		
		private function getNodeAtWaypoint(wp:Waypoint):Node
		{
			return nodes[wp.graphNodeIndex];
		}
		
		private function drawNodeArcs(node:GraphNode, target:GraphNode = null):void
		{
			var arcStart:Node = getNodeAtWaypoint(node.data);
			
			for (var i:int = 0; i < node.numArcs; i++)
			{
				var arc:GraphArc = node.arcs[i];
				var arcTarget:Node = getNodeAtWaypoint(arc.node.data);
				
				if (target && arc.node != target) continue;
				
				var dx:Number = arcTarget.x - arcStart.x;
				var dy:Number = arcTarget.y - arcStart.y;
				var len:Number = Math.sqrt(dx * dx + dy * dy);
				
				var xdir:Number = dx / len;
				var ydir:Number = dy / len;
				
				if (len < 30)
				{
					nodeCanvas.graphics.moveTo(arcStart.x + xdir * (Node.RADIUS + 4), arcStart.y + ydir * (Node.RADIUS + 4));
					nodeCanvas.graphics.lineTo(arcTarget.x - xdir * (Node.RADIUS + 4), arcTarget.y - ydir * (Node.RADIUS + 4));
				}
				else
				drawArrow(nodeCanvas.graphics, arcStart.x + xdir * (Node.RADIUS + 4), arcStart.y + ydir * (Node.RADIUS + 4),
						  xdir, ydir, len - 2 * (Node.RADIUS + 4), 4);
			}
		}
		
		private function freezeNodes(flag:Boolean):void
		{
			//enable/disable mouse events for all nodes
			for (var i:int = 0; i < nodeCanvas.numChildren; i++)
			{
				var node:Node = nodeCanvas.getChildAt(i) as Node;
				node.freeze(flag);
			}
		}
		
		private function unmarkNodes():void
		{
			//reset all nodes
			for (var i:int = 0; i < nodeCanvas.numChildren; i++)
			{
				var node:Node = nodeCanvas.getChildAt(i) as Node;
				node.unmark();
			}
		}
		
		private function drawArrow(g:Graphics, x:Number, y:Number, xdir:Number, ydir:Number, len:Number, size:Number):void
		{
			var t:Number = 1 / Math.sqrt(xdir * xdir + ydir * ydir);
			
			var ex:Number = (xdir * t * len) + x;
			var ey:Number = (ydir * t * len) + y;
			
			g.moveTo(x, y);
			g.lineTo(ex, ey);
			
			var dx:Number = (ex - x);
			var dy:Number = (ey - y);
			
			var l:Number = Math.sqrt((dx * dx) + (dy * dy));
			if (l <= 0)	return;
			
			dx /= l;
			dy /= l;
			var nx:Number = -dy;
			var ny:Number =  dx;
			g.moveTo(ex, ey);
			g.lineTo((ex - (size * dx)) - (size * nx), (ey - (size * dy)) - (size * ny));
			g.moveTo(ex, ey);
			g.lineTo((ex - (size * dx)) + (size * nx), (ey - (size * dy)) + (size * ny));
		}
	}
}
